/**
 * 109. 有序链表转换二叉搜索树
 * https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/
 */
public class Solutions_109 {
    public static void main(String[] args) {
        int[] arr = {-10, -3, 0, 5, 9};  // output: {0, -3, 9, -10, null, 5}
        ListNode head = MyLinkedListUtils.ArrayToListNode(arr);
        TreeNode result = sortedListToBST(head);
        System.out.println(result);
    }

    public static TreeNode sortedListToBST(ListNode head) {
        return dfs(head, null);
    }

    /**
     * 关键：确定查找链表的开始结点与结束结点
     */
    public static TreeNode dfs(ListNode start, ListNode end) {
        if (start == null || start == end) {
            // 结束条件：没有结点了
            return null;
        }
        // 找到链表的中间节点，来保证以中间节点为界，左右的结点个数之差最多 1 个
        if (start.next == end) {
            // 结束条件：只有一个可用结点
            return new TreeNode(start.val);
        }
        // 通过快慢指针，来找到链表的中间结点
        ListNode fast = start, slow = start;
        while (fast != end && fast.next != end) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode mid = slow;
        TreeNode root = new TreeNode(mid.val);
        // mid 的所有前驱结点，都构成 root 的左子树，所有后继结点，都构成 root 的右子树
        root.left = dfs(start, mid);
        root.right = dfs(mid.next, end);
        return root;
    }
}
